#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int n,m,q,k,fac[3000010],inv[3000010],b[3000010],a[3000010],d[300010],c[3000010],ans;
map<int,int>mp;
int ksm(int x,int y){
	int res=1;
	while(y){
		if(y&1)res=res*x%mod;
		x=x*x%mod,y>>=1;
	}
	return res;
}
void dfs(int x){
	if(x==q+1){
		for(int i=1;i<=n;i++)d[i]=0;
		for(int i=1;i<=q;i++)d[b[i]]=c[i];
//		for(int i=1;i<=q;i++)cout<<b[i]<<" "<<c[i]<<"\n";
//		cout<<"\n";
//		for(int i=1;i<=n;i++)cout<<d[i]<<" ";
//		cout<<"\n";
		for(int i=1;i+m-1<=n;i++){
			int f=1;
			for(int j=1;j<=m;j++)if(a[j]!=d[i+j-1])f=0;
			ans+=f;
		}
//		cout<<ans<<"\n";
		return;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=k;j++){
			b[x]=i,c[x]=j;
			dfs(x+1);
		}
	}
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
	cin>>n>>m>>q>>k,fac[0]=1;
	for(int i=1;i<=m;i++)fac[i]=fac[i-1]*i%mod;
	inv[m]=ksm(fac[m],mod-2);
	for(int i=m-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
	if(q<m){
		cout<<0;
	}
	else{
		for(int i=1;i<=m;i++)cin>>a[i];
		dfs(1);
		cout<<ans;
	}
	return 0;
}
/*
3 2 2 2
1 2

*/
